Contest Nowcoder1115 Nowcoder Challenge33

牛客挑战赛1115，很有难度的一些题，当然，我指的部分。

妖馨斋的五彩棒

给定三个正整数$A, B, C$。设$AA = \frac{AB}{C} + \frac{BC}{A} +\frac{AC}{B}$，$BB = A + B + C$。如果$AA > BB$输出$YES$，否则输出$NO$。

这道题我看到的时候直接笑喷了。。。又要有不少人想各种诡异的算法。实际上虽然数据范围很大，但是对于$python$来说直接暴力模拟是没有任何问题的。

n = input().split() ;
A = float(n[0])
B = float(n[1])
C = float(n[2])
    
AA = (A * B) / C + (B * C) / A + (A * C) / B
BB = A + B + C 
if AA > BB:
    print("YES")
else:
    print("NO")

鸽天的放鸽序列

给定一个$N，K$，定义一个长为$N$的$01$序列${A_i}$，其权值为$\sum_{i = 1}^{N}((\sum_{j = 1}^iA_j)~mod~2)$，求有多少个$01$序列满足有$K$个1，并且权值最大。

这个题是要好好研究一下这个式子的。

发现里面的$\sum_{j = 1}^iA_j$指的是前缀和，因为是$01$序列，因此我们可以抽象成前缀中$1$的个数，但是他后面$mod$了一个$2$，因此我们知道了，对于每一个前缀，如果含有的$1$的个数为$1$那么贡献就为$1$否则贡献为$0$。

因此我们尝试去推一下构造这个$01$序列的规律。首先我们发现如果放$0$那么是可以产生和前一位相同的贡献的，因此如果前面的$1$的个数为偶数，那么这个时候我们放$0$必然是不优的，因此直接舍弃这个转移方式。当然，如果前面是$0$个$1$的话也是一样的，同样是会浪费掉这个$0$。

因此我们尝试去构造一个$Dp$转移，设$Dp[i][j]$表示构造到了前$i$个数，并且含有$j$个$1$的满足要求的序列有多少个。那么我们有这样的转移：

$Dp[i][j] = Dp[i - 1][j]+Dp[i - 1][j - 1]~(j ~mod~ 2 == 1)$ $Dp[i][j] = Dp[i - 1][j - 1]~(j~mod~2 == 0)$

嗯，他看起来很好理解那我就不多说了，当然你也可以选择滚动数组，但是你会发现即使这样他也会超时，因此就考虑将所有的这些玩意组合起来看最后的结果。

你会发现最后的结果相当于是在$k$个$1$里面茶语$n - k$个$0$，并且这些$0$能插入的位置必须满足前缀和为奇数。因此我们一共有$\lfloor \frac{k}{2} \rfloor$可以插入，因此直接组合数即可。当然不要忘了求$Inv$。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std ;

typedef long long LL ;
const LL MAXN = 1000100 ;
const LL MAXM = 1000100 ;
const LL INF = 0x7fffffff ;
const LL Mod = 1e9 + 7 ;
LL N, K, A[MAXN], Ans, Fac[MAXN], Inv[MAXN] ;

inline LL Read() {
	LL X = 0 ; bool F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

LL quickMod(LL a,LL b) {
	LL ans = 1;
	while (b)
	{
		if (b&1)
			ans = ans * a % Mod;
		a = a*a % Mod;
		b >>= 1;
	}
	return ans;
}
 
void getFac() {
	Fac[0] = Inv[0] = 1;
	for (int i = 1 ; i <= 1000010 ; i++) {
		Fac[i] = Fac[i-1] * i % Mod;
		Inv[i] = quickMod(Fac[i],Mod-2); 
	}
}
 
LL getC(LL n,LL m) {
	return Fac[n] * Inv[n-m] % Mod * Inv[m] % Mod;
}

int main() {
	N = Read() ; K = Read() ;
	if (K == 0) {
		printf("1") ;
		return 0 ;
	}
	getFac() ;
	N = N - 2 + K % 2 ;
	K = (K - 1) / 2 ;
	printf("%lld\n", getC(N - K, K)) ;
}